
import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，
 *              即把一个数组最开始的若干个元素搬到数组的末尾，
 *              变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。
 *              请问，给定这样一个旋转数组，求数组中的最小值
 * User: 86187
 * Date: 2022-09-29
 * Time: 8:20
 */

class Solution {
    public static int  minNumberInRotateArray(ArrayList<Integer> array) {

        /*
        //法一:
        if(array == null) { return 0; }

        int left = 0, mid = 0;
        int right = array.size() - 1;

        while(left < right) {

            if(right - left == 1) {
                mid = right;
                break;
            }

            mid = left + ((right - left) >> 1 );

            if(array.get(left) == array.get(mid) && array.get(mid) == array.get(right)) {
                int result = array.get(0);
                for(int i = left+1; i < right; ++i) {
                    if(result > array.get(i)) {
                        result = array.get(i);
                    }
                }
                return result;
            }


            if(array.get(mid) >= array.get(left)) {
                left = mid;
            } else {
                right = mid;
            }
        }

        return array.get(mid);
        */

        int left = 0;
        int right = array.size() - 1;

        while(left < right) {

            int mid = left + ((right - left) >> 1);

            if(array.get(mid) > array.get(right)) {
                left = mid + 1;
            } else if(array.get(mid).equals(array.get(right))) {
                right--;
            } else {
                right = mid;
            }
        }
        return array.get(left);

    }
}

public class Test {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(0);
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(1);
        arrayList.add(1);
        System.out.println(Solution.minNumberInRotateArray(arrayList));
    }
}
